<?php
/*
 * 给定一个链表list，如果：
 * list = 1 调整之后1。
 * list = 1->2 调整之后1->2
 * list = 1->2->3 调整之后1->2->3
 * list = 1->2->3->4 调整之后1->3->2->4
 * list = 1->2->3->4->5 调整之后1->3->2->4->5
 * list = 1->2->3->4->5->6 调整之后1->4->2->5->3->6
 * list = 1->2->3->4->5->6->7 调整之后1->4->2->5->3->6->7
 * 根据上面的规律，调整一个任意长度的链表。
 */

require_once '../../../class/ListNode.class.php';
$arr = [1,2,3,4,5,6,7];
$head = array2LinkList($arr);
$obj = new Code_02_RelocationLinkedList();
$node = $obj->do($head);
fetchNode($node);

class Code_02_RelocationLinkedList
{
    /*
     * 规律：将链表分成左右两个部分，
     * 当节点数量偶数时，左右相等，结果为L1->R1->L2->R2->L3->R3
     * 当节点数量奇数时，左少右多，结果位L1->R1->L2->R2->R3
     */
    public function do($head)
    {
        if ($head == null || $head->next == null) {
            return;
        }
        $headOrigin = $head;
        $mid = $head;
		$right = $head->next;
		while ($right->next != null && $right->next->next != null) {
            $mid = $mid->next;
            $right = $right->next->next;
        }
		$right = $mid->next;
		$mid->next = null;
		$this->mergeLR($head, $right);
		return $headOrigin;
    }

    public function mergeLR($left, $right)
    {
        while ($left->next != null) {
            $next = $right->next;
            $right->next = $left->next;
            $left->next = $right;
            $left = $right->next;
            $right = $next;
        }
        $left->next = $right;
    }
}